import math
import copy

def insertion_sort(input_list):
    input_len = len(input_list)
    
    for index in range(1, input_len):
        key = input_list[index]
        compare_with = index - 1
        while compare_with >= 0 and input_list[compare_with] > key:
            input_list[compare_with + 1] = input_list[compare_with]
            compare_with -= 1
        input_list[compare_with + 1] = key

    return input_list

def merge_sort(input_list):
    def __merge(input_list, start, sep, end):
        part1 = copy.copy(input_list[start : sep])
        part2 = copy.copy(input_list[sep : end])
        part1_len = len(part1)
        part2_len = len(part2)
        part1_index = part2_index = 0
        result_index = start
       
        while part1_index < part1_len and part2_index < part2_len:
            if part1[part1_index] > part2[part2_index]:
                input_list[result_index] = part2[part2_index]
                part2_index += 1
            else:
                input_list[result_index] = part1[part1_index]
                part1_index += 1
            result_index += 1

        for index in range(part1_index, part1_len):
            input_list[result_index] = part1[index]
            result_index += 1
        for index in range(part2_index, part2_len):
            input_list[result_index] = part2[index]
            result_index += 1

    def __sort(input_list, start, end):
        input_len = end - start
        if input_len > 1:
            sep = int(math.ceil((start + end) / 2))
            __sort(input_list, start, sep)
            __sort(input_list, sep, end)
            __merge(input_list, start, sep, end)

    __sort(input_list, 0, len(input_list))
    return input_list

def bubble_sort(input_list):
    input_len = len(input_list)
    for index in range(0, input_len):
        compare_with = input_len - 1
        while compare_with > index:
            if input_list[compare_with] < input_list[compare_with - 1]:
                input_list[compare_with - 1], input_list[compare_with] = input_list[compare_with], input_list[compare_with - 1]
            compare_with -= 1
    return input_list

def heap_sort(input_list):
    from heap import max_heap
    from heap import swap_element

    h = max_heap(input_list)
    
    while h.heap_length >= 2:
        swap_element(h.array, 0, h.heap_length - 1)
        h.heap_length -= 1
        h.max_heapify(0)
    
    return input_list

def quick_sort(input_list):
    from heap import swap_element

    def __partition(input_list, p, q):
        i = p
        for j in range(p, q - 1):
            if not input_list[j] > input_list[q - 1]:
                swap_element(input_list, i, j)
                i += 1
        swap_element(input_list, i, q - 1)
        return i

    def __quick_sort(input_list, p, q):
        if q > p + 1:
            r = __partition(input_list, p, q)
            __quick_sort(input_list, p, r)
            __quick_sort(input_list, r + 1, q)
        return input_list

    return __quick_sort(input_list, 0, len(input_list))
